﻿#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;

class Solution {
private:
    const static int HALFN = 10001;
    int del_arr[HALFN * 2] = { 0 };
public:
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        vector<int> ans;
        priority_queue<int> pque;
        for (int i = 0; i < k; i++) {
            pque.push(nums[i]);
        }
        ans.push_back(pque.top());
        for (int i = k; i < nums.size(); i++) {
            int cdata = nums[i - k];
            if (pque.top() == cdata) {
                pque.pop();
            }
            else {
                del_arr[cdata + HALFN]++;
            }
            while (del_arr[pque.top() + HALFN] > 0) {
                del_arr[pque.top() + HALFN]--;
                pque.pop();
            }
            pque.push(nums[i]);
            ans.push_back(pque.top());
        }
        return ans;
    }
};

Solution solution;

int main() {
    int k = 5;
    vector<int> testdata = { 9, 10, 9, -7, -4, -8, 2, -6 };
    vector<int> ans = solution.maxSlidingWindow(testdata, k);
    for (auto i : ans) cout << i << " ";
    return 0;
}